#ifndef __LINKTREE_H_
#define __LINKTREE_H_
#include "DoubleLinkList.h"
#include <string>

class LinkTree; // 前置声明
class TreeNode  // 树的结点
{
public:
    // using ElementType = void*;
    using ElementType = std::string;      // 定义数据类型
    TreeNode(const ElementType &element); // 带参构造：初始化双亲、孩子、兄弟指针为空，传入数据给data；
    void Connect(TreeNode *parent);       // 将一个节点绑定成另一个节点的孩子
    void Disconnect(TreeNode *parent);    // 解绑
    TreeNode *Getparent() { return parent; }
    friend LinkTree; // 友元声明
    ElementType GetData() { return data; }
    void SetData(const ElementType &element) { data = element; }

private:
    ElementType data;     // 数据域
    TreeNode *parent;     // 双亲节点
    TreeNode *firstChild; // 第一个孩子指针    (由第一个孩子指针指向兄弟)
    TreeNode *nextSbling; // 下一个兄弟指针
};

class LinkTree
{
public:
    using ElementType = TreeNode::ElementType;

    LinkTree();
    ~LinkTree();
    TreeNode *GetRoot() { return root; }
    void show();

    DoubleLinkList FindByElement(const ElementType &element);
    int GetTreeHeight(); // 获取树的高度
    int Size();          // 统计树中结点数量
    // 统计树中叶子结点数量
    int leaves();

private:
    void GetNodeLeave(TreeNode *node, int &count);  // 获取叶子数量
    void GetNodeSize(TreeNode *node, int &count);   // 节点数量
    int GetNodeHeight(TreeNode *node);   // 高度
    void FindNode(TreeNode *node, const ElementType &element, DoubleLinkList &list); 
    void show(TreeNode *node, int deepth);
    void FreeNode(TreeNode *node);  // 
    TreeNode *root; // 根结点
};

#endif
